#include <stdio.h>
#include <stdlib.h>

char *a;

int i;

typedef struct Tnode* link;

struct Tnode {
    char token;
    link l;
    link r;
};

link NEW(char token, link l, link r);
link parse();

void printnode(char c, int h);
void show(link x, int h);
void visit(link h);
void trav_in(link h, void(*visit)(link));
void trav_post(link h, void(*visit)(link));
void visit_codegen(link h);

int main(){
    i = 0;
    char input[] = {'*', '+', 'a', '*', '*', 'b', 'c', '+', 'd', 'e', 'f'};
    a = input;
    //构建前缀表达式对应的解析树
    link root = parse();
    // show(root, 4);
    //中序遍历得到对应的中缀表达式
    trav_in(root, visit);
    printf("\n");
    //后序遍历得到对应的后缀表达式
    trav_post(root, visit);
    printf("\n");
    //后序遍历生成对应的求值机器码
    trav_post(root, visit_codegen);
    return 0;
}

void show(link x, int h){
    if (x == NULL) {
        printnode('*', h);
        return ;
    }
    show(x->r, h+1);
    printnode(x->token, h);
    show(x->l, h+1);
}

void printnode(char c, int h){
    int j;

    for (j = 0; j < h; j++) {
        printf("  ");
    }
    printf("%c\n", c);
}

link NEW(char token, link l, link r){
    link x = malloc(sizeof(*x));
    x->token = token;
    x->l = l;
    x->r = r;

    return x;
}
link parse(){
    char t = a[i++];
    link x = NEW(t, NULL, NULL);
    if ((t == '*') || t == '+') {
        x->l = parse();
        x->r = parse();
    }
    return x;
}

void visit(link h){
    printf("%c ", h->token);
}

void trav_in(link h, void(*visit)(link)){
    if (h == NULL) {
        return ;
    }
    trav_in(h->l,visit);
    (*visit)(h);
    trav_in(h->r, visit);
}

void trav_post(link h, void(*visit)(link)){
    if (h == NULL) {
        return ;
    }
    trav_post(h->l,visit);
    trav_post(h->r, visit);
    (*visit)(h);
}

void visit_codegen(link h){
    if (h == NULL) {
        return ;
    }
    if (h->token == '*') {
        printf("MULTIPLY\n");
    }else if (h->token == '+') {
        printf("ADD\n");
    }else {
        printf("LOAD %c\n", h->token);
    }
}
